In graph theory, a uniquely colorable graph is a k-chromatic graph that has only one possible (proper) k-coloring up to permutation of the colors.
Contents |
A complete graph is uniquely colorable, because the only proper coloring is one that assigns each vertex a different color.
Every k-tree is uniquely (k + 1)-colorable. The uniquely 4-colorable planar graphs are known to be exactly the Apollonian networks, that is, the planar 3-trees (Fowler 1998).
Some properties of a uniquely k-colorable graph G with n vertices and m edges:
A minimal imperfect graph is a graph in which every subgraph is perfect. The deletion of any vertex from a minimal imperfect graph leaves a uniquely colorable subgraph.
A uniquely edge-colorable graph is a k-edge-chromatic graph that has only one possible (proper) k-edge-coloring up to permutation of the colors. The only uniquely 2-edge-colorable graphs are the paths and the cycles. For any k, the stars K1,k are uniquely k-edge-colorable graphs. Moreover, Wilson (1967) conjectured and Thomason (1978) proved that, when k ≥ 4, they are also the only members in this family. However, there exist uniquely 3-edge-colorable graphs that do not fit into this classification, such as the graph of the triangular pyramid. The generalized Petersen graph G(9,2) is the only known nonplanar uniquely 3-edge-colorable graph, and it has been conjectured that it is the only such graph. See Bollobás (1978) and Schwenk (1989).
A uniquely total colorable graph is a k-total-chromatic graph that has only one possible (proper) k-total-coloring up to permutation of the colors.
Empty graphs, paths, and cycles of length divisible by 3 are uniquely total colorable graphs. Mahmoodian & Shokrollahi (1995) conjectured that they are also the only members in this family.
Some properties of a uniquely k-total-colorable graph G with n vertices:
Here χ″(G) is the total chromatic number; Δ(G), maximum degree; and δ(G), minimum degree.